# class Solution(object):
#     def subArrayRanges(self, nums):
#         n = len(nums)
#         pre_min = [0] * n
#         pre_max = [0] * n
#         suff_min = [0] * n
#         suff_max = [0] * n
#         min_st = []
#         max_st = []
#         for i in range(n):
#             while min_st and nums[i] <= nums[min_st[-1]]:
#                 min_st.pop()
#             if min_st:
#                 pre_min[i] = i - min_st[-1] - 1
#             else:
#                 pre_min[i] = i
#             min_st.append(i)
#             while max_st and nums[i] >= nums[max_st[-1]]:
#                 max_st.pop()
#             if max_st:
#                 pre_max[i] = i - max_st[-1] - 1
#             else:
#                 pre_max[i] = i
#             max_st.append(i)
#         min_st = []
#         max_st = []
#         for i in range(n - 1, -1, -1):
#             while min_st and nums[i] < nums[min_st[-1]]:
#                 min_st.pop()
#             if min_st:
#                 suff_min[i] = min_st[-1] - i - 1
#             else:
#                 suff_min[i] = n - 1 - i
#             min_st.append(i)
#             while max_st and nums[i] > nums[max_st[-1]]:
#                 max_st.pop()
#             if max_st:
#                 suff_max[i] = max_st[-1] - i - 1
#             else:
#                 suff_max[i] = n - 1 - i
#             max_st.append(i)
#         ans = 0
#         for i in range(n):
#             ans += nums[i] * ((pre_max[i] + 1) * (suff_max[i] + 1) - (pre_min[i] + 1) * (suff_min[i] + 1))
#         return ans

class Solution():
    def subArrayRanges(self, nums):
        min_st = []
        min_t = 0
        max_t = 0
        min_ans = 0
        max_ans = 0
        max_st = []
        for num in nums:
            c = 1
            while min_st and num <= min_st[-1][0]:
                val, count = min_st.pop()
                c += count
                min_t -= val * count
            min_st.append([num, c])
            min_t += num * c
            min_ans += min_t
            c = 1
            while max_st and num >= max_st[-1][0]:
                val, count = max_st.pop()
                c += count
                max_t -= val * count
            max_st.append([num, c])
            max_t += num * c
            max_ans += max_t
        return max_ans - min_ans


data = Solution()
nums = [4, -2, -3, 4, 1]
print(data.subArrayRanges(nums))
